package String;

import org.junit.Test;

/**
 * @Classname JZ19正则表达式匹配
 * @Description TODO
 * @Date 2022/12/10 11:47
 * @Created by xjl
 */
public class JZ19正则表达式匹配 {
    /**
     * @description 如果是两个无序的字符 需要判断相关的问题 需要考虑的时候转为二维数组进而来思考动态规划的问题。
     * @param: s
     * @param: p
     * @date: 2022/12/10 12:04
     * @return: boolean
     * @author: xjl
     */
    public boolean isMatch(String s, String p) {
        int m = s.length() + 1, n = p.length() + 1;
        boolean[][] dp = new boolean[m][n];
        dp[0][0] = true;
        // 初始化首行结果
        for (int j = 2; j < n; j += 2) {
            dp[0][j] = dp[0][j - 2] && p.charAt(j - 1) == '*';
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = p.charAt(j - 1) == '*' ?
                        dp[i][j - 2] || dp[i - 1][j] && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.') :
                        dp[i - 1][j - 1] && (p.charAt(j - 1) == '.' || s.charAt(i - 1) == p.charAt(j - 1));
            }
        }
        return dp[m - 1][n - 1];
    }

    @Test
    public void test(){
        String s="aaa";
        String p="ab*.*";
        boolean match = isMatch(s, p);
    }
}
